// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
// Created by ade on 2022/9/8.
//
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {};

};

class Solution {
public:
    // 时间复杂度 2log(N) 这个方法还不是最好的
    vector<TreeNode *> v = {};
    unordered_map<TreeNode *, int> m = {};
    TreeNode *res;

    TreeNode *lowestCommonAncestor1(TreeNode *root, TreeNode *p, TreeNode *q) {
        dfs(root);
        for (int i = 0; i < v.size(); i++) m[v[i]] = i;
        getNode(root, min(m[p], m[q]), max(m[p], m[q]));
        return res;
    }

    void getNode(TreeNode *node, const int &minV, const int &maxV) {
        if (!node) return;
        if (m[node] >= minV && m[node] <= maxV) {
            res = node;
            return;
        }
        if (m[node] < minV) {
            getNode(node->right, minV, maxV);
        } else {
            getNode(node->left, minV, maxV);
        }
    }

    void dfs(TreeNode *root) {
        if (!root)return;
        dfs(root->left);
        v.push_back(root);
        dfs(root->right);
    }


    // 官方解法
    TreeNode *ans;

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        findNode(root, p, q);
        return ans;
    }

    bool findNode(TreeNode *node, TreeNode *p, TreeNode *q) {
        if (!node)return false;
        bool l = findNode(node->left, p, q);
        bool r = findNode(node->right, p, q);
        if ((l && r) ||
            (node->val == q->val || node->val == p->val) && (l || r)) {
            ans = node;
        }
        return l || r || node->val == p->val || node->val == q->val;
    }


};
